package com.leetcode.专项突破.排序算法全解析;

import com.leetcode.common.utils.ArrayUtils;
import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author 覃国强
 * @date 2022-05-12 17:17
 */
public class B02_快速排序 {

  public static void main(String[] args) {
    QuickSort quickSort = new QuickSort();
    int[] arr = ArrayUtils.randomArr(20);
    System.out.println("origin: " + Arrays.toString(arr));
    quickSort.sort(arr);
    System.out.println("sorted: " + Arrays.toString(arr));
  }

  static class QuickSort {

    public void sort(int[] arr) {
      sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int start, int end) {
      if (start < end) {
        int pivot = partition(arr, start, end);
        sort(arr, start, pivot - 1);
        sort(arr, pivot + 1, end);
      }
    }

    private int partition(int[] arr, int start, int end) {
      // 选取随机一个元素作为基数
      int pivot = ThreadLocalRandom.current().nextInt(start, end + 1);
      // 将基数放到最后的位置（这个位置的选择会影响到下面循环体的逻辑）
      swap(arr, pivot, end);
      pivot = end;
      // end 向前一步
      --end;

      while (start <= end) {
        // 从前往后找到第一个大于基数的位置
        while (start <= end && arr[start] <= arr[pivot]) {
          ++start;
        }
        // 交换基数与该位置的数
        swap(arr, start, pivot);
        pivot = start;
        // start 向后一步
        ++start;

        // 此处的判断非常重要，因为此时 start <= end 条件可能已经不满足了，所以不能再进行交换
        if (start <= end) {
          // 从后往前找到第一个小于基数的位置
          while (start <= end && arr[end] >= arr[pivot]) {
            --end;
          }
          // 交换基数与该位置的数
          swap(arr, end, pivot);
          pivot = end;
          // end 向前一步
          --end;
        }
      }

      return pivot;
    }

    private void swap(int[] arr, int i, int j) {
      if (i != j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }

  }


}
